// Problem 133: Repunit nonfactors
//
// A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.
// Let us consider repunits of the form R(10^n).
// Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10^n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10^n).
// Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10^n).
//----
//Find the R(k) that is divisible by prime p, if k only has factors 2 and/or 5, then p can be divisor of R(10^n).
package main

import (
	"fmt"
	"projecteuler/euler"
)

func p133() {
	sum_all := 0
	sum_can := 11 + 17 + 41 + 73
	euler.FillPrime(100000)
	for _, i := range euler.PrimeList {
		sum_all += i
		if i < 100 {
			continue
		}
		if check133(a133(i)) {
			sum_can += i
		}
	}

	fmt.Println("Problem 133:", sum_all-sum_can)
}

func a133(n int) int {
	bit := 2
	remainder := 11 % n
	for remainder != 0 {
		remainder = (remainder*10 + 1) % n
		bit += 1
	}
	return bit
}
func check133(n int) bool {
	for n%2 == 0 {
		n /= 2
	}
	for n%5 == 0 {
		n /= 5
	}
	return n == 1
}
